A very large data store system may be implemented as a distributed data store such that data is stored on a plurality of separate memory devices, for example separate disk drives. Such disk drives are sometimes referred to as back end data storage. Client applications may read and write the data in the distributed data stores, and the distributed data store may map these access requests to the appropriate memory devices. As the number of data entries in the data store may increase over time, it may be desirable to add one or more additional memory devices and redistribute some of the data entries from legacy memory devices to the one or more additional or new memory devices. Sometimes memory devices may be decommissioned and/or removed from service as the device exceeds an expected service life or as the device begins to experience failures. In case of memory device decommissioning or removal, the data entries on the subject memory device may desirably be migrated to other memory devices.